package com.zjsru.plan2023.oneday;

/**
 * @Author: cookLee
 * @Date: 2023-12-02
 * 拼车
 * 给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
 */
public class CarPooling {

    /**
     * 主
     * \
     * 输入：trips = [[2,1,5],[3,3,7]], capacity = 4
     * 输出：false
     * \
     * 输入：trips = [[2,1,5],[3,3,7]], capacity = 5
     * 输出：true
     * \
     * @param args args
     */
    public static void main(String[] args) {
        CarPooling carPooling = new CarPooling();
        int[][] trips = new int[][]{{2, 1, 5}, {3, 3, 7}};
        int capacity = 4;
        System.out.println(carPooling.carPooling(trips, capacity));
    }


    /**
     * 拼车
     * 差分数组
     *
     * @param trips    trips
     * @param capacity 容量
     * @return boolean
     */
    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[trips.length];
        //获取每个站点上下车的人数组成差分数组
        for (int[] trip : trips) {
            diff[trip[1]] += trip[0];
            diff[trip[2]] -= trip[0];
        }
        int curr = 0;
        int len = diff.length;
        //每个差分数组的节点的累计 即是承受的总人数
        for (int i = 0; i < len; i++) {
            curr += diff[i];
            if (curr > capacity) {
                return false;
            }
        }
        return true;
    }

}
